package 动态规划;

import java.util.Arrays;

public class 背包问题 {
	
	public static void main(String[] args) {
		
	/*
	 * 有n个物品，它们有各自的体积和价值，现有给定容量的背包，
	 * 如何让背包里装入的物品具有最大的价值总和？
	 
	   最多可以放4公斤的物品
	   物品1: 1公斤   价值1500元
	   物品2: 4公斤   价值3000元
	   物品3: 3公斤   价值2000元

	  使用动态规划思想求解：首先拆分子问题，将子问题结果填表，之后可以直接取值
	  表的列表示某物品，表的行表示背包此时的最大容量
	 
	  编号/体积	0		1	 	2	 	3		4
	    0		0		0		0	 	0		0
	    1		0		1500 	1500 	1500 	1500
	    2		0		1500	1500	1500	3000
	    3		0		1500	1500	2000	2000+1500
	 */
		
		
		//注意weight、value都是3位，而v[][]是4位，会造成不同步现象，所以要-1！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
		//weight表示每件物品重量
		int[] weight = {1,4,3};//{0,1,4,3}这样下面就不用weight-1了，因为和v[][]同步了
		//int[] weight = {2,3,4,5};
		//value表示每件物品价值
		int[] value = {1500,3000,2000};//{0,1500,3000,2000}这样下面就不用value-1了，因为和v[][]同步了
		//int[] value = {3,4,5,6};
		
		//背包容量
		int m = 4;
		//物品个数
		int n = value.length;
		
		//定义二维数组v，表示动太规划表，v[i][j]表示当前第i个物品，对应背包容量为j时 的最大价值
		//声明时要多一行一列，表示全0，边界
		int[][] v = new int[n+1][m+1];
		
		//当背包容量为0时，此列全为0
		for(int i = 0; i < v.length; i++) {
			v[i][0] = 0;
		}
		//当物品为0时，背包中价值为0
		for(int i = 0; i < v[0].length; i++) {
			v[0][i] = 0;
		}
		
		//动态处理
		//不处理第一行，从1开始
		for(int i = 1; i < v.length; i++) {
			//不处理第一列，从1开始
			for(int j = 1; j < v[0].length; j++) {
				
				//从第一个开始，如果此物品体积weight[i]大于背包容量j，放不下，就放上一个容量的最大价值结果
				//注意weight，weight数组，这个数组第一个不是0，不能和v数组同步 ，使用时要减去1
				if(weight[i-1] > j) {
					//放不下，放上一层最优解
					v[i][j] = v[i-1][j];
				}else {
					//放的下，背包正好等于或大于物品体积，取一个最大价值结果
					//v[i - 1][j]：不放当前物品，取上一层最优解
					//value[i] + v[i - 1][j - weight[i]]：放入当前物品，并且用背包容量减去当前值后，
					//从剩下的容量中像上层找最优解
					v[i][j] = Math.max(v[i - 1][j], value[i-1] + v[i - 1][j - weight[i-1]]);
				}
			}
		}
		
		//输出
		for(int i = 0; i < v.length; i++) {
			for(int j = 0; j < v[i].length; j++) {
				System.out.print(v[i][j] + "  ");
			}
			System.out.println();
		}
		
		//对于回溯得到背包中是哪几个物品，有两种方法
		//1.是在放入背包时，添加到记录数组中
		//2.得到最后结果后，向前回溯
		
		//记录数组，注意是否同步，不加1，就在下面减1
		int[] item = new int[n+1];
		//得到背包容量
		int j = m;
		//回溯
		for(int i = n ;i > 0; i--) {
			//当前解，大于上一层的解，表示当前值被算进去了
			if (v[i][j] > v[i - 1][j]) {
				//记录当前商品,位置为1
				item[i] = 1;
				//计算剩余空间，得到剩余空间的那层最优解，注意weight[i-1]不同步，继续回溯
				j = j - weight[i-1];
			}
		}
		
		System.out.print("背包中物品最大价值"+v[n][m]+" ,物品编号：");
		for (int i = 0; i < item.length; i++) {
			if(item[i] == 1) {
				System.out.print(i+" ");
			}
		}
	}

}

/**
 *  背包问题
 * @author PC
 *
 */
class DPBackpack{
	
	
}
